package com.ww.springboot.boot.algorithm.leetcode1;

/**
 * 描述：
 *
 * @author 🧑 ‍wanwei
 * @since 2022-04-19 17:09
 */
public class BQ105从前序与中序遍历序列构造二叉树 {

    public static void main(String[] args) {
        int[] preorder = {-1};
        int[] inorder = {-1};
        System.out.println(buildTree(preorder, inorder));
    }

    /**
     * 前序遍历   根节点 [左子树的前序遍历] [右子树的前序遍历]
     * <p>
     * 中序遍历   [左子树的中序遍历] 根节点 [右子树的中序遍历]
     * 1.根据前序遍历 找到根节点
     * 2.根据中序遍历找到根节点后切分左子树和右子数
     *
     * @param preorder
     * @param inorder
     * @return
     */
    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        TreeNode treeNode = new TreeNode();

        int preorderStart = 0;
        int preorderEnd = preorder.length - 1;
        int inorderStart = 0;
        int inorderEnd = inorder.length - 1;
        buildTree(preorderStart, preorderEnd, inorderStart, inorderEnd, preorder, inorder, treeNode);
        return treeNode;
    }

    /**
     * 前序遍历   根节点 [左子树的前序遍历] [右子树的前序遍历]
     * 中序遍历   [左子树的中序遍历] 根节点 [右子树的中序遍历]
     *
     * @param preorder
     * @param inorder
     * @return
     */
    private static void buildTree(int preorderStart, int preorderEnd, int inorderStart, int inorderEnd, int[] preorder, int[] inorder, TreeNode treeNode) {
        treeNode.val = preorder[preorderStart];
        int index = 0;
        for (int i = inorderStart; i < inorderEnd; i++) {
            if (inorder[i] == preorder[preorderStart]) {
                break;
            }
            index++;
        }
        if(index > 0){
            TreeNode treeNodeLeft = new TreeNode();
            treeNode.left = treeNodeLeft;
            buildTree(preorderStart + 1, preorderStart + 1 + index-1, inorderStart, inorderStart + index-1, preorder, inorder, treeNode.left);
        }
        if(inorderStart + index < inorderEnd){
            TreeNode treeNodeRight = new TreeNode();
            treeNode.right = treeNodeRight;
            buildTree(preorderStart + 1 + index, preorderEnd, inorderStart+1 + index, inorderEnd, preorder, inorder, treeNode.right);
        }

    }


    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }
}
